/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ZhongJinTao
 * Date: 2024-10-06
 * Time: 10:52
 */
public class Sort {
    public void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    // 单向选择排序
    public void selectSort(int[] arr) {
        int n = arr.length;
        for(int i = 0; i < n; i++) {
            int min = i;
            for(int j = i + 1; j < n; j++) {
                if(arr[j] < arr[min]) {
                    min = j;
                }
            }
            swap(arr, i, min);
        }
    }

    // 双向选择排序
    public void selectSort2(int[] arr) {
        int n = arr.length, left = 0, right = n -1;
        while (left < right) {
            int min = left, max = left;
            for(int i = left + 1; i <= right; i++) {
                if(arr[i] < arr[min]) {
                    min = i;
                }
                if(arr[i] > arr[max]) {
                    max = i;
                }
            }
            swap(arr, left, min);
            // 防止第一个是最大值
            // 如果和最小值一换，最大值就跑到最小值的下标那了
            if(left == max) max = min;
            swap(arr, right, max);
            left++;
            right--;
        }
    }

    // 冒泡排序
    public void bubbleSort(int[] arr) {
        int n = arr.length;

        for(int i = 0; i < n - 1; i++) {
            boolean flag = false;
            for (int j = 0; j < n - 1 - i; j++) {
                if(arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    flag = true;
                }
            }
            // 说明根本没有进行交换，该数组已经是有序的了，那么就直接跳出循环
            if(!flag) break;
        }
    }

    // 快速排序
    public void quickSort(int[] arr) {
        if (arr == null || arr.length == 0) return; // 检查输入
        int start = 0, end = arr.length - 1;
        quick(arr, start, end);
    }
    public void quick(int[] arr, int start, int end) {
        if(start >= end) return;
        int pivot = partitionHoare(arr, start, end);
        quick(arr, start, pivot - 1);
        quick(arr, pivot + 1, end);
    }
    public int partitionHoare(int[] arr, int left, int right) {
        int flag = left;//记录下标
        int tmp = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= tmp) {
                right--;
            }
            while (left < right && arr[left] <= tmp) {
                left++;
            }
            swap(arr, left, right);
        }
        swap(arr, flag, left);
        return left;
    }
    // 归并排序
    public void mergeSort(int[] arr) {
        mergeSortFun(arr, 0, arr.length - 1);
    }
    public void mergeSortFun(int[] arr, int start, int end) {
        if(start >= end) {
            return;
        }
        int mid = (start + end) / 2;
        mergeSortFun(arr, start, mid);
        mergeSortFun(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }
    public void merge(int[] arr, int left, int mid, int right) {
        int s1 = left, e1 = mid, s2 = mid + 1, e2 = right;
        int[] tmp = new int[right - left + 1];
        int cur = 0;
        while (s1 <= e1 && s2 <= e2) {
            if(arr[s1] <= arr[s2]) {
                tmp[cur] = arr[s1++];
            } else {
                tmp[cur] = arr[s2++];
            }
            cur++;
        }
        while (s1 <= e1) {
            tmp[cur++] = arr[s1++];
        }
        while (s2 <= e2) {
            tmp[cur++] = arr[s2++];
        }
        for (int i = 0; i < tmp.length; i++) {
            arr[i + left] = tmp[i];
        }
    }
}
